#ifndef DIJKSTRA_H
#define DIJKSTRA_H

#include "PriorityQueue.h"

// From stdint.h since it's not avaiable on windows.
#define INT32_MAX         2147483647

#include <vector>

namespace algo {
  static size_t comps;
  class DijkstraNode;
  class DijkstraHeapNode;

  class DijkstraEdge {
  public:
    DijkstraEdge(DijkstraNode *to, int weight) : to(to), weight(weight) {}
  private:
    friend class DijkstraNode;
    friend class Dijkstra;
    DijkstraNode *to;
    int weight;
  };

  class DijkstraNode {
  public:  
    DijkstraNode() : distance(INT32_MAX), predecessor(0), queueNode(0) {}

    DijkstraNode(int distance) : distance(distance), predecessor(0), queueNode(0) {}
    

    void reset() {
      distance = INT32_MAX;
      predecessor = 0;
      queueNode = 0;
    }

    void addEdge(DijkstraNode *node, int weight) {
      DijkstraEdge edge(node, weight);
      edges.push_back(edge);
    }

    int getDistance() const { return distance; }

    DijkstraNode *getPredecessor() const { return predecessor; }

  private:
    friend class Dijkstra;
    friend class DijkstraHeapNode;
    std::vector<DijkstraEdge> edges;
    int distance;
    DijkstraNode *predecessor;
    PriorityQueueNode<DijkstraHeapNode> *queueNode;
  };

  class DijkstraHeapNode {
  public:
    DijkstraHeapNode(DijkstraNode* node) : node(node) {}
    DijkstraHeapNode() : node(0) {}

    bool operator==(const DijkstraHeapNode &other) {
      comps++;
      if (!node || !other.node)
        return false;
      return node->distance == other.node->distance;
    }

    bool operator<(const DijkstraHeapNode &other) {
      comps++;
      if (!node)
        return true;
      if (!other.node)
        return false;
      return node->distance < other.node->distance;
    }

     bool operator<=(const DijkstraHeapNode &other) {
      comps++;
      if (!node)
        return true;
      if (!other.node)
        return false;
      return node->distance <= other.node->distance;
    }

    bool operator!=(const DijkstraHeapNode &other) {
      comps++;
      if (!node || !other.node)
        return true;
      return node->distance != other.node->distance;
    }

    DijkstraNode &operator->() {
      return *node;
    }

    DijkstraNode *operator*() {
      return node;
    }

    DijkstraNode *node;
  private:
    friend class Dijkstra;
  };

  class Dijkstra {
  public:
    Dijkstra(PriorityQueue<DijkstraHeapNode> *Q, const std::vector<DijkstraNode*> &nodes)
      : Q(Q), nodes(nodes) {}

    void run(DijkstraNode* source) {
      source->distance = 0;

      for (size_t i = 0; i < nodes.size(); i++) {
        nodes[i]->queueNode = Q->insert(nodes[i]);
      }

      while (DijkstraNode *u = *Q->deleteMin()) {
        if (u->distance == INT32_MAX)
          continue;

        for (size_t i = 0; i < u->edges.size(); i++) {
          int dist = u->distance + u->edges[i].weight;
          DijkstraNode *v = u->edges[i].to;

          if (dist < u->edges[i].to->distance) {
            v->distance = dist;
            v->predecessor = u;
            Q->decreaseKey(v->queueNode, v);
          }
        }
      }
    }

  private:
    PriorityQueue<DijkstraHeapNode> *Q;
    std::vector<DijkstraNode*> nodes;
  };
}

#endif //DIJKSTRA_H
